#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include "PriorityQueue.h"
using namespace std;


//150. 逆波兰表达式求值
//https://leetcode.cn/problems/evaluate-reverse-polish-notation/

/*
class Solution {
public:
    static int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for (auto str : tokens) {
            if (str == "+" || str == "-" || str == "*" || str == "/"){
                int right = st.top();
                st.pop();
                int left = st.top();
                st.pop();
                switch (str[0]) {
                    case '+':
                        st.push(left + right);
                        break;
                    case '-':
                        st.push(left - right);
                        break;
                    case '*':
                        st.push(left * right);
                        break;
                    case '/':
                        st.push(left / right);
                        break;
                }
            } else
                st.push(atoi(str.c_str()));
        }
        return st.top();
    }
};

void test1(){
    vector<string> token;
    token.emplace_back("2");
    token.emplace_back("1");
    token.emplace_back("+");
    token.emplace_back("3");
    token.emplace_back("*");
    cout << Solution::evalRPN(token);
}
*/

void test_priority_queue(){
    //优先级队列：默认大堆，降序
    priority_queue<int> pq;
    pq.push(2);
    pq.push(9);
    pq.push(6);
    pq.push(8);
    pq.push(5);
    while (!pq.empty()){
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;

    //添加仿函数，改为小堆，升序
    priority_queue<int, vector<int>, greater<int>> pq2;
    pq2.push(2);
    pq2.push(9);
    pq2.push(6);
    pq2.push(8);
    pq2.push(5);
    while (!pq2.empty()){
        cout << pq2.top() << " ";
        pq2.pop();
    }
    cout << endl;
}

template<class T>
struct Less{
    bool operator()(const T& x, const T& y){
        return x < y;
    }
};

void test_functional(){
    Less<int> less_func;
    cout << less_func(5,3) << endl;
}


//215. 数组中的第K个最大元素
//https://leetcode.cn/problems/kth-largest-element-in-an-array/

/*
class Solution {
public:
    static int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() - k];
    }
};
*/

/*
class Solution {
public:
    static int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq(nums.begin(), nums.end());
        while (--k){
            pq.pop();
        }
        return pq.top();
    }
};
*/

class Solution {
public:
    static int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.begin() + k);
        for (size_t i = k; i < nums.size(); ++i) {
            if (nums[i] > pq.top()){
                pq.pop();
                pq.push(nums[i]);
            }
        }
        return pq.top();
    }
};

void test_homework1()
{
    stack<char> S;
    char x,y;
    x='n';y='g';
    S.push(x);S.push('i');S.push(y);
    S.pop();S.push('r');S.push('t');S.push(x);
    S.pop();S.push('s');
    while(!S.empty())
    {
        x = S.top();
        S.pop();
        cout<<x;
    };
    cout<<y;

}

void test_homework2()
{
    queue<char> Q;
    char x,y;
    x='n';y='g';
    Q.push(x);
    Q.push('i');
    Q.push(y);
    Q.pop();
    Q.push('r');
    Q.push('t');
    Q.push(x);
    Q.pop();
    Q.push('s');
    while(!Q.empty())
    {
        x = Q.front();
        Q.pop();
        cout<<x;
    };
    cout<<y;
}

int main() {
    //test1();
    //test_priority_queue();
    //test_functional();
    //Lu::test_priority_queue2();
    test_homework2();
    return 0;
}
